//
// Created by TNJ on 2021/6/20.
//
#include "merge_sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void merge(data_type_t *src, int left, int mid, int right, data_type_t *temp){
    if(src == NULL || temp == NULL){
        return;
    }
    int i = left, j = mid + 1;
    int index = 0;

    while(i <= mid && j <= right){
        if(src[i] < src[j]){
            temp[index++] = src[i++];
        }else{
            temp[index++] = src[j++];
        }
    }
    if(i <= mid){
        //将剩余左边部分拷贝到临时缓冲区
        memcpy(&temp[index], &src[i], (mid - i + 1) * sizeof(data_type_t));
    }
    if(j <= right){
        //将右边剩余部分拷贝到临时缓冲区
        memcpy(&temp[index], &src[j], (right - j + 1) * sizeof(data_type_t));
    }
    //将临时缓冲区的内容拷贝到原始缓冲区中
    memcpy(&src[left], temp, (right - left + 1) * sizeof(data_type_t));
    for(i = left; i <= right; i++){
        printf("%d ", src[i]);
    }
    printf("\n");
}

void merge_sort(data_type_t *src, int left, int right, data_type_t *temp){
    if(src == NULL || temp == NULL || left >= right){
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(src, left, mid, temp);
    merge_sort(src, mid + 1, right, temp);
    merge(src, left, mid, right, temp);
}